class Solution {
public:
    // 利用堆的思想——TOPK问题
    // int findKthLargest(vector<int>& nums, int k) 
    // {
    //     priority_queue<int,vector<int>,less<int>> pq(nums.begin(),nums.end());
        
    //     int n = k;
    //     while(--n)
    //     {
    //         pq.pop();
    //     }
    //     return pq.top();
    // }

    //利用快排选择算法
    int findKthLargest(vector<int>& nums, int k) 
    {
        srand(time(0));
        return qsort(nums,0, nums.size()- 1, k);
    }

    int qsort(vector<int>& nums, int l,int r, int k)
    {
        if(l == r) 
            return nums[l];

        //随机选key
        int key = getRandom(nums,l,r);
        
        //三路划分
        int i = l, right = r + 1,left = l - 1;
        while(i < right)
        {
            if(nums[i] < key) 
                swap(nums[++left],nums[i++]);
            else if(nums[i] ==  key)
                i++;
            else
                swap(nums[--right],nums[i]);
        }

        //分情况讨论
        int c = r -  right + 1, b = right - left - 1;
        if(c >= k) 
            return qsort(nums,right,r,k);
        else if(b + c >= k)
            return key;
        else
            return qsort(nums,l,left,k-b-c);
    }

    int getRandom(vector<int>& nums,int l, int r)
    {
        return  nums[rand() % (r - l + 1) + l];
    }
};


class Solution {
public:
    // //排序
    // vector<int> inventoryManagement(vector<int>& stock, int cnt) 
    // {
    //     sort(stock.begin(),stock.end());
    //     vector<int> res;
    //     for(int i = 0; i < cnt ; i++)
    //         res.push_back(stock[i]);
    //     return res;
    // }

    //快速选择
     vector<int> inventoryManagement(vector<int>& stock, int cnt) 
    {
        srand(time(nullptr));
        qsort(stock, 0, stock.size() - 1, cnt);
        return {stock.begin(), stock.begin() + cnt};
    }

    void qsort(vector<int>& nums, int l, int r, int k)
    {
        if(l >= r) 
            return;

        //随机选key
        int key = getRandom(nums,l,r);
        //三路划分
        int left = l - 1, right = r + 1, i = l;
        while(i < right)
        {
            if(nums[i] < key)
                swap(nums[++left], nums[i++]);
            else if(nums[i] == key)
                i++;
            else
                swap(nums[--right],nums[i]);
        }

        //分情况讨论
        int a = left - l + 1, b = right - left - 1;
        if(a > k)
            qsort(nums,l,left,k);
        else if(a + b >= k)
            return;
        else 
            qsort(nums,right,r,k - a - b);
    }

    int getRandom(vector<int>& nums, int l, int r)
    {
        return nums[rand() % (r - l + 1) + l];
    }
};

class Solution
{
public:
    vector<int> tmp;//辅助归并
    vector<int> sortArray(vector<int>& nums)
    {
        tmp.resize(nums.size());
        mergesort(nums, 0, nums.size()- 1);
        return nums;
    }

    void mergesort(vector<int>& nums, int left, int right)
    {
        if(left >= right)
            return;
        
        //划分区间 [left, mid][mid + 1, right]
        int mid = (right + left) >> 1;

        //递归分治
        mergesort(nums, left, mid);
        mergesort(nums, mid + 1, right);

        //排序
        int cur1 = left, cur2 = mid + 1, i = 0;
        while(cur1 <= mid && cur2 <= right)
            tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];
        
        while(cur1 <= mid) 
            tmp[i++] = nums[cur1++];
        while(cur2 <= right)
            tmp[i++] = nums[cur2++];

        //写回原数组
        for(int i = left; i <= right; i++)
            nums[i] = tmp[i - left];
    }
};
class Solution {
public:
    int tmp[50001];//辅助数组
    int reversePairs(vector<int>& record) 
    {
        return mergeSort(record,0,record.size() - 1);
    }

    int mergeSort(vector<int>& nums, int left, int right)
    {
        if(left >= right)
            return 0;
        
        //拆分数组
        int mid = (left + right) >> 1;
        int ret = 0;//记录逆序对

        //左边数组+排序 + 右边数组+排序
        ret += mergeSort(nums,left,mid);
        ret += mergeSort(nums,mid+1,right);

        int cur1 = left, cur2 = mid + 1, i = 0;//i 用于遍历辅助数组
        
        while(cur1 <= mid && cur2 <= right)
        {
            if(nums[cur1] <= nums[cur2])
            {
                tmp[i++] = nums[cur2++];
            }
            else
            {
                ret += right - cur2 + 1;//关键一步
                tmp[i++] = nums[cur1++];
            }
        }

        //处理待排序区间
        while(cur1 <= mid) tmp[i++] = nums[cur1++];
        while(cur2 <= right) tmp[i++] = nums[cur2++];

        //写回原数组
        for(int i = left; i <= right; i++)
            nums[i] = tmp[i - left];
        return ret;

    }   
};


class Solution {
public:
    vector<int> ret,index;
    int tmpIndex[999999];
    int tmp[999999];

    vector<int> countSmaller(vector<int>& nums) 
    {
        int n = nums.size();
        ret.resize(n);
        index.resize(n);
        for(int i = 0; i < n; i++)
        {
            index[i] = i;
        }
        mergeSort(nums,0,nums.size() - 1);
        return ret;
    }
    void mergeSort(vector<int>& nums,int left, int right)
    {
        if(left >= right)
            return;
        
        int mid = (left + right) >> 1;

        mergeSort(nums,left,mid);
        mergeSort(nums,mid+1,right);

        int cur1 = left, cur2 =mid + 1, i = 0;
        while(cur1 <= mid && cur2 <= right)
        {
            if(nums[cur1] <= nums[cur2])
            {
                tmp[i] = nums[cur2];
                tmpIndex[i++] = index[cur2++];
            }
            else
            {
                ret[index[cur1]] += right - cur2 + 1;
                tmp[i] = nums[cur1];
                tmpIndex[i++] = index[cur1++];
            }
        }

        while(cur1 <= mid) 
        {
            tmp[i] = nums[cur1];
            tmpIndex[i++] = index[cur1++];
        }
        while(cur2 <= right)
        {
            tmp[i] = nums[cur2];
            tmpIndex[i++] = index[cur2++];
        }

        for(int j = left; j <= right; j++)
        {
            nums[j] = tmp[j-left];
            index[j] = tmpIndex[j-left];
        }
    }

};